/*
https://leetcode-cn.com/problems/super-egg-drop/solution/ji-dan-diao-luo-by-leetcode-solution-2/
 */
import java.util.Arrays;

public class Solution887 {
    public int superEggDrop(int k, int n) {
        int[][] f=new int[k+1][n+1];
        for (int[] ints : f) {
            Arrays.fill(ints,-1);
        }
        return dp(k,n,f);
    }

    private int dp(int k, int n,int[][] f) {
        if (f[k][n]==-1){
            int ans=0;
            if (n==0){
                ans=0;
            }else if (k==1){
                ans=n;
            }else{
                int l=1,r=n;
                while (l+1<r){
                    int mid=(l+r)/2;
                    int t1=dp(k-1,mid-1,f);
                    int t2=dp(k,n-mid,f);
                    if (t1<t2){
                        l=mid;
                    }else if (t1>t2){
                        r=mid;
                    }else{
                        l=r=mid;
                    }
                }
                ans=1+Math.min(Math.max(dp(k-1,l-1,f),dp(k,n-l,f)),Math.max(dp(k-1,r-1,f),dp(k,n-r,f)));
            }
            f[k][n]=ans;
        }
        return f[k][n];
    }

    public static void main(String[] args) {
        System.out.println(new Solution887().superEggDrop(3,14));
    }

}
